# 1155. 掷骰子等于目标和的方法数
class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        MOD = 10 ** 9 + 7

        @cache
        def dfs(i, cur_sum):
            if cur_sum < i:
                return 0
            if i == 0:
                return cur_sum == 0 if 1 else 0
            cur = 0
            for j in range(1, k + 1):
                cur += dfs(i - 1, cur_sum - j) % MOD
            return cur % MOD

        return dfs(n, target)
